/*
 * @lc app=leetcode.cn id=621 lang=cpp
 *
 * [621] 任务调度器
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        // greedy

        // <task, num>
        std::unordered_map<char, int> hashTask;
        for (auto task : tasks){
            hashTask[task] ++ ;
        }

        // todo : 
        // std::priority_queue<int> taskQueue;

        // sort task by num, maybe A=5 and B=5, so multi
        std::multimap<int, char, std::greater<int>> sortedTaskMap;
        for (auto pair : hashTask){
            sortedTaskMap.emplace(pair.second, pair.first);
        }

// default : std::less => increasing order
// now     : std::greater => descending order

// for (auto info : sortedTaskMap){
//     printf("(%d %c) ", info.first, info.second);
// }
        
        int usedTaskFlag[26];

        // 1 circle = n task pierods, search max task to fill in
        int circle = 0;

        // check task left
        while (sortedTaskMap.rbegin()->first != 0){
            // start circle
            circle += 1;
            memset(usedTaskFlag, 0, 26*sizeof(int));

            // while
            // current circle task num < n
            // and can find a not used task

            // do
            // find task, mark used, erase and emplace pair
            
            auto maxNumTask = sortedTaskMap.begin();
            while (usedTaskFlag[maxNumTask->second - 'A'] != 0){
                maxNumTask ++;
            }
        }

        return circle * n;
    }
};
// @lc code=end

